ЕГЭ Информатика
Задачи на теорию игр строятся вокруг идеи выигрышных и проигрышных позиций. Дадим им определения:
Выигрышная позиция для X — такое состояние игры, при котором существует способ (комбинация возможных ходов) выиграть для игрока X.
Выигрышная позиция (в общем) — выигрышная позиция для требуемого в задаче игрока.
Проигрышная позиция для X — такое состояние игры, при котором не существует способов (комбинации возможных ходов) выиграть для игрока X.
Проигрышная позиция (в общем) — проигрышная позиция для требуемого в задаче игрока.
Классическая модель ходов предусматривает два условия:
Рассмотрим такой пример.
Два игрока: П и В
Начинает: П
Условие победы: наличие в куче ≥ 13 камней
Побеждает: последний
Ходы: +1, +2, +3
Ограничение на кучу:
Начало рассмотрения — всегда наиболее близкие к победе позиции. Начинаем с 12. Очевидно, что при П побеждает, т.к. любой ход ведёт к победе. При существует хотя бы один возможный ход, ведущий к победе. Однако при нет ни одного хода, который бы вёл к победе одним ходом, т.е. ход в любом случае перейдёт к противнику.
Полезно заметить, что можно абстрагироваться от конкретных игроков и текущего номера хода. Рассмотрим :
На шаге 2 мы имеем , выигрышную позицию для П, если П начинает игру, и проигрышную, если начинает игру В. То есть справедливо обобщение:
— выигрышные позиции для того игрока, который из них начинает ход.
Обменяв роли, легко показать, что та же логика сохраняется и для : она проигрышная для игрока, который из неё начинает ход.
Рассмотрим значения далее. За обозначим ход игрока , слева будет значение S к началу хода, справа — к концу.
Можно заметить, что все выигрышные стратегии строятся на том, что к ходу противника мы приводим его в проигрышную позицию (). Проигрышные позиции же имеют другую общую особенность: все ходы ведут в выигрышную позицию для противника. Обобщим:
Пусть — выигрышная позиция для того, кто из неё начинает ход. Пусть — проигрышная позиция для того, кто из неё начинает ход. Пусть — тип позиции при значении кучи .
, для всех таких, что есть хотя бы один ход, переводящий , где попадает под определение победы.
Затем определим на оставшихся :
, если существует хотя бы один ход такой, что .
, если не существует ни одного хода такого, что
Из этих же соображений можно вывести обратную логику:
Если для какого-то , то .
Существуют задачи, в которых набор ходов может зависеть от текущего значения S. Определим множество ходов на некоторое . Каждый ход обозначим функцией , преобразующей в . Соответственно . Тогда обобщение перехода:
,
.
Заметим, что классическая модель ходов — частный случай зависимости от , при котором .
При зависимости набора возможных ходов не только от S, но и от номера конкретного хода (в том числе и от конкретного игрока), введём понятие полухода:
Полуход — ход одного игрока.
Тогда игра из, например, 3 ходов, в которой побеждает первый игрок, состоит из 5 полуходов:
Вместе с этим определим:
Номер игрока, которому принадлежит полуход — (тогда номера игроков 0 и 1). Номер хода конкретного игрока для полухода (начиная с 0) — .
Для удобства будем нумеровать и ходы, и игроков с 0.
Тогда функция принимает два аргумента: .
Пусть — тип позиции при значении кучи перед началом полухода .
Поскольку каждый ход переводит игру к следующему полуходу (), а значит, передает право хода противнику, логика перехода сохраняется, но с учетом увеличения номера полухода:
.
Существуют вариации задач с формулировками вида «противник совершит неудачный ход».
Неудачный ход — такой ход, который приводит в выигрышную для противника позицию, при том что существовали другие возможные ходы, приводившие противника в проигрышную позицию.
Наличие неудачного хода требует переформулирования условий перехода:
, если существует хотя бы один ход такой, что .
, если существует хотя бы один ход такого, что
Эту же логику легко применить и к моделям с зависимыми ходами.
Для оптимизации решений, скорее всего, вы захотите считать ходы программным способом. Опишем модель зависимых от S ходов на Python для такой задачи:
Два игрока: П и В
Начинает: П
Условие победы: .
Побеждает: последний
Ходы:
- , если и
- , если и
- , если и
- , если и
Ограничение на кучу:
Опишем M с той лишь разницей, что она будет возвращать значения сразу же:
def M(s):
if s % 2 == 0:
if s % 3 == 0:
ms = [s // 2, s // 3]
else:
ms = [s // 2, s - 3]
else:
if s % 3 == 0:
ms = [s - 2, s // 3]
else:
ms = [s - 2, s - 3]
# отбросим ходы, опускающие кучу ниже условия победы
return [m for m in ms if m >= 1]
G имеет свои нюансы реализации. Так как требуется найти не выигрышность/проигрышность ситуации при старте из неё (как это делает G в нашей математической модели), а ответить на вопрос «получится ли выиграть у игрока p своим i-тым ходом», то немного изменим её реализацию.
Заметим, что условие «получится ли выиграть у игрока p своим i-тым ходом» можно легко переформулировать через понятие полухода:
Игрок выигрывает своим -тым ходом полуход — выигрышный, а игра завершается на следующем, т.е. полуходе. (при условии нумерации и с нуля).
Соответственно, реализуем G как функцию от текущего состояния кучи S и номера полухода n:
def G(s, m):
if s == 1: # условие победы
return m % 2 == 0 # ДОЛЖЕН победить игрок с p = 0 (П.)
if m == 0 or s < 1: # проверка краевого случая
return 0
h = [G(s_, m - 1) for s_ in M(s)]
if not h: # не осталось возможных ходов
return 0
# Если сейчас наш ход — ищем хотя бы один путь к победе (any)
# Если ход противника — победа должна быть при любом его ходе (all)
return any(h) if (m - 1) % 2 == 0 else all(h)
Допустим, если необходимо проверить, можно ли победить Ване () своим вторым () ходом при камней в куче, проверим значение G(S, 4), т.к. .